﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Drawing.Drawing2D;
using System.Windows.Forms;
using System.Threading;
namespace MMDemo
{
    /// <summary>
    /// 图的操作类型
    /// </summary>
    enum GraphsOperateType
    {
        BFT = 61,//广度优先遍历
        DFT = 62,//深度优先遍历
        Prim = 63,//Prim算法生成最小生成树
        Kruskal = 64,//Kruskal 算法生成最小生成树
        TopologicalSortCheckLoop = 65,//使用拓朴排序检查有向图是否有回路
        DFTCheckLoop = 66,//深度优先检查有向图是否有回路
        Dijkstra  = 67,//单顶点最短路径,非负数
        Bellman_Ford = 68,//单顶点最短路径 ，任意权值
    }
    /// <summary>
    /// 线两端的结点及权限
    /// </summary>
    public struct LineSideVertex
    {
        public int vertex_one;
        public int vertex_two;
        public int cost;
        public LineSideVertex(int vertex_one, int vertex_two, int cost)
        {
            this.vertex_one = vertex_one;
            this.vertex_two = vertex_two;
            this.cost = cost;
        }
        public void SetValues(int vertex_one, int vertex_two, int cost)
        {
            this.vertex_one = vertex_one;
            this.vertex_two = vertex_two;
            this.cost = cost;
        }
    }
    public class VertexComparer : IComparer<LineSideVertex>
    {
        public int Compare(LineSideVertex x, LineSideVertex y)
        {
           return x.vertex_one.CompareTo(y.vertex_one);
        }
    }
    public struct ShortPath
    {
       public  int vertex;//顶点
       public int dist;//距离
       public int path;//路径
       public void SetValues(int vertex, int dist, int path)
       {
           this.vertex = vertex;
           this.dist = dist;
           this.path = path;
       }
    }
    /// <summary>
    /// 图论
    /// </summary>
    class AnimationGraphs:InterfaceDataStructs
    {
        private List<string> Save_Path = new List<string>();
        /// <summary>
        /// 表格的高度，用于最短路径
        /// </summary>
        private int Form_Height = 245;
        /// <summary>
        /// 画图矩阵的第一个元素的大小
        /// </summary>
        private Size Maxtrix_Elment_Size = new Size(50, 45);
        /// <summary>
        /// 动画演示的默认执行速度
        /// </summary>
        private const int DEFAULT_SPEED = 500;
        /// <summary>
        /// 最大的权值
        /// </summary>
        private const int MAX_COST = 500;
        /// <summary>
        /// 是否是无权图
        /// </summary>
        private bool UnCost = true;
        /// <summary>
        /// 是否是无向图
        /// </summary>
        private bool UnDirectGraph = true;
        /// <summary>
        /// 图的结点数
        /// </summary>
        private int VertexNum = 0;
        /// <summary>
        /// 图的矩阵
        /// </summary>
        private int[,] GraphMatrix;
        /// <summary>
        /// 保存图中的线，以及线两端的结点和权限
        /// </summary>
        private List<LineSideVertex> LSN = new List<LineSideVertex>();
        /// <summary>
        /// 被访问的邻接边
        /// </summary>
        private List<LineSideVertex> VisitLSN = new List<LineSideVertex>();
        /// <summary>
        /// 在Kruskal算法生成最小生成树用来保存没有被选中的边的和拓朴排序
        /// </summary>
        private List<LineSideVertex> CopyLSN = new List<LineSideVertex>();
        /// <summary>
        /// 结点的大小(48*48)
        /// </summary>
        private int VertexSize = 48;
        /// <summary>
        /// 结点不同图片
        /// </summary>
        private Bitmap[]VertexBmp;
        /// <summary>
        /// 有多少个不同各类结点图片
        /// </summary>
        private const int VERTEXBMP_NUM = 3;
        /// <summary>
        /// 双缓冲Graphics
        /// </summary>
        private Graphics BufferGraph = null;
        /// <summary>
        /// 双缓冲画布
        /// </summary>
        private Bitmap BufferBmp = null;
        /// <summary>
        /// 动画窗口的高度
        /// </summary>
        private int An_Width = 0;
        /// <summary>
        /// 动画窗口的宽度
        /// </summary>
        private int An_Height = 0;
        private Form An_Form = null;
        /// <summary>
        /// 委托的句柄
        /// </summary>
        private DrawHandler An_Handler = null;
        /// <summary>
        /// 结点是否被访问
        /// </summary>
        private int[] visit;
        /// <summary>
        /// 用做于深度遍历的栈和广度遍历的队列
        /// </summary>
        private List<int> LineList = new List<int>();
        /// <summary>
        /// 当前结点
        /// </summary>
        private int v = 0;
        /// <summary>
        /// 圆的半径
        /// </summary>
        private int radius = 0;
        /// <summary>
        /// 操作类型
        /// </summary>
        private GraphsOperateType operateType = GraphsOperateType.BFT;
        /// <summary>
        /// 执行速度
        /// </summary>
        private int Speed = DEFAULT_SPEED;
        /// <summary>
        /// 用于深度优先算法，
        /// </summary>
        private int PtrVertex = 0;
        /// <summary>
        /// 箭头图片
        /// </summary>
        private Bitmap arrowBmp = null;
        /// <summary>
        /// 保存顶点，用于最小生成树 
        /// </summary>
        private List<int> vertexs = new List<int>();
        /// <summary>
        /// 保存不同连通分量的顶点
        /// </summary>
        private String strCCvertex = "";
        /// <summary>
        /// 遍历的结果 
        /// </summary>
        private String visitResult = "";
        /// <summary>
        /// 拓朴排序的结果
        /// </summary>
        private String TopologicalSortResult = "";
        /// <summary>
        /// 圆的中心点的坐标
        /// </summary>
        private Point CenterPt = new Point();
        /// <summary>
        /// 保存最短路径 
        /// </summary>
        private ShortPath[] ShortPathes;
        /// <summary>
        /// 是不是最大化，根据这个值来显示图的是矩阵还是边
        /// </summary>
        private bool bMaximize = false;
        public AnimationGraphs(Form An_Form, DrawHandler refreshHandler, int An_Width, int An_Height)
        {
            this.An_Form = An_Form;
            this.An_Handler = refreshHandler;
            this.An_Width = An_Width;
            this.An_Height = An_Height;

            VertexBmp = new Bitmap[VERTEXBMP_NUM];
            LoadBitmap();
            BufferBmp = new Bitmap(An_Width, An_Height);
            BufferGraph = Graphics.FromImage(BufferBmp);
        }
        public void SetCenterPoint()
        {

        }
        /// <summary>
        /// 加载结点图片
        /// </summary> 
        private void LoadBitmap()
        {
            String path = Application.StartupPath;
            String []VertexBmpName = {"node_seven.png", "node_eight.png", "node_nine.png"};
            String bmpPath = "";
            for(int i = 0; i < VERTEXBMP_NUM; ++i)
            {
                bmpPath = path + "/image/" + VertexBmpName[i];
                VertexBmp[i] = (Bitmap)Image.FromFile(bmpPath);
            }
            arrowBmp = (Bitmap)Image.FromFile(path + "/image/deletepos.png");
        }
        /// <summary>
        /// 显示被访问的顶点和边
        /// </summary>
        private void Visit()
        {
            ShowGraphs(BufferGraph);
            Refresh();
        }
        /// <summary>
        /// 求箭头的坐标
        /// </summary>
        private Point SetArrowPoint(Point StartPt, Point EndPt)
        {
            Point ArrowPt = EndPt;
            int OffsetX = 0, OffsetY = 0;
            int Width = EndPt.X - StartPt.X;
            int Height = EndPt.Y - StartPt.Y;
            //对角线的长度
            int diagonal = (int)Math.Sqrt(Width * Width + Height * Height);
            int r = VertexSize / 2;
            OffsetX = -r * Width / diagonal;
            OffsetY = -r * Height / diagonal;
            ArrowPt.X += OffsetX;
            ArrowPt.Y += OffsetY;
            return ArrowPt;
        }
        /// <summary>
        /// 删除与vertex相邻的边
        /// </summary>
        /// <param name="vertex"></param>
        private void DeleteNearEdge(int vertex)
        {
            if (CopyLSN.Count == 0)
            {
                return;
            }
            for (int i = 0; i < CopyLSN.Count; ++i)
            {
                if (CopyLSN[i].vertex_one == vertex)
                {
                    GraphMatrix[CopyLSN[i].vertex_one, CopyLSN[i].vertex_two] = 0;
                    VisitLSN.Add(new LineSideVertex(CopyLSN[i].vertex_one, CopyLSN[i].vertex_two, 1));
                    CopyLSN.RemoveAt(i);
                    --i;
                }
            }
        }
        /// <summary>
        /// 判断该顶点是否有出度
        /// </summary>
        private bool IsHaveInDegree(int vertex)
        {
            for (int i = 0; i < VertexNum; ++i)
            {
                if (GraphMatrix[i, vertex] != 0)
                {
                    return true;
                }
            }
            return false;
        }
        private int FindEdgeInVisit(int vertexOne, int vertexTwo)
        {
            for (int i = 0; i < VisitLSN.Count; ++i)
            {
                if (VisitLSN[i].vertex_one == vertexOne && VisitLSN[i].vertex_two == vertexTwo)
                {
                    return -1;
                }
            }
            if (IsExsitInStack(vertexTwo))
            {
                EnStack(vertexTwo);
                VisitLSN.Add(new LineSideVertex(vertexOne, vertexTwo, 1));
                return 0;
            }
            return 1;
        }
        private int GetVertex(int vertex)
        {
            for (int i = 0; i < VertexNum; ++i)
            {
                if (GraphMatrix[vertex, i] != 0)
                {
                    int flag = FindEdgeInVisit(vertex, i);
                    if (flag == 0)
                    {
                        return -2;
                    }
                    else if (flag == 1 && visit[i] == 0)
                    {
                        return i;
                    }
                }
            }
            return -1;
        }
        /// <summary>
        /// 深度优先检查是否有回路
        /// </summary>
        private void DFTCheckLoop()
        {
            InitVisit();
            LineListClear();
            VisitLSN.Clear();
            SetExcuteLine(3);
            for (int v = 0; v < VertexNum; ++v)
            {
                SetExcuteLine(5);
                if (0 == visit[v])//如果没有被访问，则访问该点
                {
                    SetExcuteLine(7);
                    EnStack(v);
                    visit[v] = 1;
                    Visit();
                    int vertex;
                    SetExcuteLine(10);
                    while (!IsLineListEmpty())
                    {
                        ////是否还有没有被访问的邻接点
                        vertex = LineList[0];
                        PtrVertex = vertex;
                        SetExcuteLine(12);
                        vertex = GetVertex(vertex);
                        SetExcuteLine(13);
                        if (-2 == vertex)
                        {
                            Visit();
                            SetExcuteLine(29);
                            MessageBox.Show(An_Form, "有回路存在!");
                            return;
                        }
                        else if (-1 == vertex)
                        {
                            SetExcuteLine(20);
                            QuitStack();
                            if (0 != LineList.Count)
                            {
                                PtrVertex = LineList[0];
                            }
                        }
                        else
                        {
                            SetExcuteLine(24);
                            EnStack(vertex);
                            visit[vertex] = 1;
                            VisitLSN.Add(new LineSideVertex(PtrVertex, vertex, 1));
                        }
                        Visit();
                        SetExcuteLine(10);
                    }
                }
                SetExcuteLine(3);
            }
            SetExcuteLine(29);
            MessageBox.Show(An_Form, "无环路存在");
        }
        /// <summary>
        /// 拓朴排序检查是否有回路
        /// </summary>
        private void TopologicalSortCheckLoop()
        {
            TopologicalSortResult = "";
            InitGraphsMaxtrix();
            SetGraphsMaxtrix();
            List<int> tempVertex = new List<int>();
            CopyLSN.Clear();
            GlobalGraphs.LSN.ForEach(i => CopyLSN.Add(i));
            for (int i = 0; i < VertexNum; ++i)
            {
                tempVertex.Add(i);
            }
            SetExcuteLine(3);
            while (true)
            {
                SetExcuteLine(5);
                bool bOutDegree = false;
                SetExcuteLine(6);
                for (int i = 0; i < tempVertex.Count; ++i)
                {
                    SetExcuteLine(8);
                    bOutDegree = IsHaveInDegree(tempVertex[i]);
                    visit[tempVertex[i]] = 2;
                    Visit();
                    SetExcuteLine(9);
                    if (!bOutDegree)
                    {
                        visit[tempVertex[i]] = 1;
                        SetExcuteLine(12);
                        DeleteNearEdge(tempVertex[i]);
                        Visit();
                        SetExcuteLine(13);
                        TopologicalSortResult += tempVertex[i].ToString();
                        tempVertex.RemoveAt(i);
                        Visit();
                        SetExcuteLine(14);
                        SetExcuteLine(15);
                        break;
                    }
                    else
                    {
                        visit[tempVertex[i]] = 0;
                        SetExcuteLine(6);
                    }   
                }
                SetExcuteLine(18);
                if (bOutDegree)
                {
                    Visit();
                    SetExcuteLine(20);
                    SetExcuteLine(24);
                    MessageBox.Show(An_Form, "有环路存在");
                    return;
                }
                if (tempVertex.Count == 0)
                {
                    SetExcuteLine(24);
                    MessageBox.Show(An_Form, "演算动画结束,无环路存在!");
                    return;
                }
                SetExcuteLine(3);
            }
        }
        /// <summary>
        /// 查找CopyLSN中权值最小的边
        /// </summary>
        /// <returns>返回该边在CopyLSN中的索引</returns>
        private int FindLowCostSide()
        {
            if (CopyLSN.Count == 0)
            {
                return -1;
            }
            //设置最小的权值为第一条边
            int index = 0;
            int lowcost = CopyLSN[0].cost;
            for (int i = 1; i < CopyLSN.Count; ++i)
            {
                if (CopyLSN[i].cost < lowcost)
                {
                    lowcost = CopyLSN[i].cost;
                    index = i;
                }
            }
            return index;
        }
        /// <summary>
        /// 根据CopyLSN边的索引判断两端顶点是否在同一连通分量中(CC is connected components)
        /// </summary>
        private bool IsVertexInSameCC(int index)
        {
            bool bResult = true;
            if (index == -1)
            {
                return true;
            }
            int ccIndexOne = -1;
            int ccIndexTwo = -1;
            String vertexOne = CopyLSN[index].vertex_one.ToString();
            String vertexTwo = CopyLSN[index].vertex_two.ToString();
            String[] ccVerters = strCCvertex.Split('|');
            strCCvertex = "";
            for (int i = 0; i < ccVerters.Length; ++i)
            {
                if (ccVerters[i].IndexOf(vertexOne) != -1 || ccVerters[i].IndexOf(vertexTwo) != -1)
                {
                    if (ccVerters[i].IndexOf(vertexOne) != -1)
                    {
                        ccIndexOne = i;
                    }
                    if (ccVerters[i].IndexOf(vertexTwo) != -1)
                    {
                        ccIndexTwo = i;
                    }
                    if (ccIndexOne != -1 && ccIndexTwo != -1)
                    {
                        if (ccIndexOne == ccIndexTwo)
                        {
                            strCCvertex += ccVerters[i] + "|";
                            bResult = true;
                        }
                        else
                        {
                            strCCvertex += ccVerters[ccIndexOne] + ccVerters[ccIndexTwo] + "|";
                            bResult = false;
                        }
                    }
                }
                else
                {
                    strCCvertex += ccVerters[i] + "|";
                }
            }
            //去掉最后一个|
            strCCvertex.Remove(strCCvertex.Length - 1);
            return bResult;
        }
        /// <summary>
        /// 初始化不同连通分量
        /// </summary>
        private void InitCCVertexs()
        {
            strCCvertex = "";
            for(int i = 0; i <VertexNum - 1; ++i)
            {
                strCCvertex += i.ToString() + "|";
            }
            strCCvertex += (VertexNum-1).ToString();
        }
        /// <summary>
        /// Kruskal 算法生成最小生成树
        /// </summary>
        private void Kruskal()
        {
            CopyLSN.Clear();
            GlobalGraphs.LSN.ForEach(elment => CopyLSN.Add(elment));
            int i = 0;
            SetExcuteLine(4);
            while (i < VertexNum - 1)
            {
                SetExcuteLine(7);
                int index = FindLowCostSide();
                if (index == -1)
                {
                    MessageBox.Show(An_Form, "没有要访问的边！");
                    break; 
                }
                SetExcuteLine(8);
                if (!IsVertexInSameCC(index))
                {
                    SetExcuteLine(11);
                    visit[CopyLSN[index].vertex_one] = 1;
                    visit[CopyLSN[index].vertex_two] = 1;
                    VisitLSN.Add(CopyLSN[index]);
                    Visit();
                    ++i;
                }
                CopyLSN.RemoveAt(index);
                SetExcuteLine(14);
                SetExcuteLine(4);
            }
            SetExcuteLine(16);
            MessageBox.Show(An_Form, "算法演示结束！");
        }
        /// <summary>
        /// 查找顶点是否在vertexs中存在
        /// </summary>
        private bool IsVertexExsit(int n)
        {
            for (int i = 0; i < vertexs.Count; ++i)
            {
                if (n == vertexs[i])
                {
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// 查找最小cost顶点
        /// </summary>
        private bool FindNextLowCostVertex()
        {
            int cost = MAX_COST;
            int nearVertex = -1;
            int vertexOne = 0, vertexTwo = 0;
            for (int i = 0; i < vertexs.Count; ++i)
            {
                nearVertex = FindLowCostVertex(vertexs[i]);
                if (nearVertex == -2)
                {
                    return false;
                }
                else if (nearVertex != -1)
                {
                    if (cost > GraphMatrix[vertexs[i], nearVertex])
                    {
                        cost = GraphMatrix[vertexs[i], nearVertex];
                        vertexOne = vertexs[i];
                        vertexTwo = nearVertex;
                    }
                }
            }
            vertexs.Add(vertexTwo);
            VisitLSN.Add(new LineSideVertex(vertexOne, vertexTwo, GraphMatrix[vertexOne, vertexTwo]));
            visit[vertexTwo] = 1;
            return true;
        }
        /// <summary>
        /// 查找与vertex相邻cost最小的顶点
        /// </summary>
        private int FindLowCostVertex(int vertex)
        {
            int lowcost = MAX_COST;
            int resultVertex = -1;
            int zerocostcount = 0;
            for (int i = 0; i < VertexNum; ++i)
            {
                if (GraphMatrix[vertex, i] < lowcost && GraphMatrix[vertex, i] != 0 && !IsVertexExsit(i))
                {
                    lowcost = GraphMatrix[vertex, i];
                    resultVertex = i;
                }
                if (GraphMatrix[vertex, i] == 0)
                {
                    zerocostcount++;
                }
            }
            if (zerocostcount == VertexNum)
            {
                resultVertex = -2;
            }
            return resultVertex;
        }
        /// <summary>
        /// prim算法生成最小生成树
        /// </summary>
        private void Prim()
        {
            InitVisit();
            vertexs.Clear();
            VisitLSN.Clear();
            Visit();
            Thread.Sleep(Speed);
            vertexs.Add(0);
            SetExcuteLine(4);
            visit[0] = 1;
            Visit();
            SetExcuteLine(5);
            SetExcuteLine(7);
            for (int i = 0; i < VertexNum - 1; ++i)
            {
                SetExcuteLine(10);
                SetExcuteLine(12);
                if (FindNextLowCostVertex())
                {
                    SetExcuteLine(14);
                    SetExcuteLine(15);
                    Visit();
                }
                else
                {
                    MessageBox.Show(An_Form, "图不是连通的，算法结束！");
                    return;
                }
                SetExcuteLine(7);
            }
            SetExcuteLine(18);
            MessageBox.Show(An_Form, "算法结束！");
        }
        /// <summary>
        /// 得到与顶点v相邻没有被访问的点
        /// </summary>
        /// <param name="v"></param>
        /// <returns></returns>
        private int GetUnVisitNeighbor(int v)
        {
            for (int i = 0; i < VertexNum; ++i)
            {
                if (0 != GraphMatrix[v, i] && 0 == visit[i])//如果还有没有被访问的顶点
                {
                    return i;
                }
            }
            return -1;
        }
        /// <summary>
        /// 深度优先算法
        /// </summary>
        private void DFT()
        {
            visitResult = "";
            SetExcuteLine(3);
            InitVisit();      
            LineListClear();
            VisitLSN.Clear();
            SetExcuteLine(4);
            for (int v = 0; v< VertexNum; ++v)
            {
                SetExcuteLine(6);
                if (0 == visit[v])//如果没有被访问，则访问该点
                {
                   
                    SetExcuteLine(8);
                    EnStack(v);
                    Visit();
                    SetExcuteLine(9);
                    PtrVertex = v;
                    Visit();
                    SetExcuteLine(10);
                    visit[v] = 1;
                    visitResult += v.ToString();
                    Visit();
                    int vertex;
                    SetExcuteLine(11);
                    while (!IsLineListEmpty())
                    {
                        ////是否还有没有被访问的邻接点
                        //bool IsHaveNoVisitNearVertex = false;
                        vertex = LineList[0];
                        SetExcuteLine(13);
                        vertex = GetUnVisitNeighbor(vertex);
                        SetExcuteLine(14);
                        if (-1 != vertex)//有没有被访问的相邻顶点
                        {
                            SetExcuteLine(16);
                            EnStack(vertex);
                            Visit();
                            SetExcuteLine(17);
                            PtrVertex = vertex;
                            visit[PtrVertex] = 1;
                            visitResult += PtrVertex.ToString();
                            VisitLSN.Add(new LineSideVertex(vertex, PtrVertex, 1));
                            Visit();
                        }
                        else//如果没有相邻的顶点，则该顶点退栈
                        {
                            SetExcuteLine(21);
                            QuitStack();
                            Visit();
                            if (0 != LineList.Count)
                            {
                                PtrVertex = LineList[0];
                            }  
                            SetExcuteLine(22);
                            Visit();
                        }
                        SetExcuteLine(11);
                    }
                }
                SetExcuteLine(4);
            }
            SetExcuteLine(27);
            MessageBox.Show(An_Form, "深度优先算法结束");
        }
        private void SetExcuteLine(int line)
        {
            Thread.Sleep(Speed);
            SysMainForm.AnimationForm.SetSelectLine(line);
        }
        /// <summary>
        /// 广度优先遍历
        /// </summary>
        private void BFT()
        {
            InitVisit();
            SetExcuteLine(3);
            LineListClear();
            visitResult = "";
            for (v = 0; v < VertexNum; ++v)
            {
                SetExcuteLine(4);
                SetExcuteLine(6);
                if (0 == visit[v])
                {
                    SetExcuteLine(8);
                    EnQueue(v);
                    Visit();
                    SetExcuteLine(9);
                    visit[v] = 1;
                    visitResult += v.ToString();
                    //访问结点visit(v)须添加
                    Visit();
                    while(!IsLineListEmpty())
                    {   
                        SetExcuteLine(10);
                        SetExcuteLine(12);
                        int vertex = QuitQueue();
                        Visit();
                        SetExcuteLine(13);
                        SetExcuteLine(14);
                        int w = GetNeighbor(vertex, 0);
                        while (w != -1)
                        {
                            SetExcuteLine(16);
                            if (0 == visit[w])//如果邻接顶点没有访问则加入队列，并访问顶点
                            {
                                //保存访问的邻接边
                                LineSideVertex tempLSN = new LineSideVertex();
                                tempLSN.vertex_one = vertex;
                                tempLSN.vertex_two = w;
                                VisitLSN.Add(tempLSN);
                                SetExcuteLine(18);
                                EnQueue(w);
                                Visit();
                                SetExcuteLine(19);
                                visit[w] = 1;
                                visitResult += w.ToString();
                                //访问结点visit(v)须添加
                                Visit();
                            }
                            SetExcuteLine(21);
                            w = GetNeighbor(vertex, w + 1);
                            SetExcuteLine(14);
                        }
                    }
                }
            }
            SetExcuteLine(26);
            MessageBox.Show(An_Form, "广度优先算法结束");
        }
        private int GetNeighbor(int v, int w)
        {
            for (int i = w; i < VertexNum; ++i)
            {
                if (GraphMatrix[v, i] != 0)
                {
                    return i;
                }
            }
            return -1;
        }
        /// <summary>
        /// 初始化访问标志
        /// </summary>
        private void InitVisit()
        {
            for(int i = 0; i < VertexNum; ++i)
            {
                visit[i] = 0;
            }
        }
        /// <summary>
        /// 线性表的清空
        /// </summary>
        private void LineListClear()
        {
            LineList.Clear();
        }
        /// <summary>
        /// 进队列
        /// </summary>
        private void EnQueue(int data)
        {
            LineList.Add(data);
        }
        /// <summary>
        /// 出队列
        /// </summary>
        private int QuitQueue()
        {
            if (0 == LineList.Count)
            {
                return -1;
            }
            int vertex = LineList[0];
            LineList.RemoveAt(0);
            return vertex;
        }
        /// <summary>
        /// 进栈
        /// </summary>
        /// <param name="data"></param>
        private void EnStack(int data)
        {
            LineList.Insert(0, data);
        }
        private bool IsExsitInStack(int data)
        {
            for (int i = 0; i < LineList.Count; ++i)
            {
                if (LineList[i] == data)
                {
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// 出栈
        /// </summary>
        private int  QuitStack()
        {
            if (0 == LineList.Count)
            {
                return -1;
            }
            int vertex = LineList[0];
            LineList.RemoveAt(0);
            return vertex;
        }
        /// <summary>
        /// 是否为空
        /// </summary>
        private bool IsLineListEmpty()
        {
            if (0 == LineList.Count)
            {
                return true;
            }
            return false;
        }
        /// <summary>
        /// 根据第几个结点得到结点的坐标
        /// </summary>
        
        private Point GetVertexPoint(int n)
        {
            double degrees = 180.0 + n * 360 / VertexNum;
            double angle = GetAngle(degrees);
            Point nodePt = new Point();
            nodePt.X = CenterPt.X + (int)(radius * Math.Cos(angle));
            nodePt.Y = CenterPt.Y + (int)(radius * Math.Sin(angle));
            return nodePt;
        }
        /// <summary>
        /// 得到圆的半径
        /// </summary>
        private int GetCircleRadius(int Width, int Height)
        {
            int radius = 0;
            //圆的直径
            int diaMeter = Width > Height ? Height : Width;
            radius = diaMeter / 2 - VertexSize / 2;
            return radius;
        }
        private double GetAngle(double degrees)
        {
            return Math.PI * degrees / 180.0;
        }
        private int FindVisitSide(int vertexOne, int vertexTwo)
        {
            for (int i = 0; i < VisitLSN.Count; ++i)
            {
                if (UnDirectGraph)
                {
                    if (vertexOne == VisitLSN[i].vertex_one && vertexTwo == VisitLSN[i].vertex_two
                        || vertexTwo == VisitLSN[i].vertex_one && vertexOne == VisitLSN[i].vertex_two)
                    {
                        return i;
                    }
                }
                else
                {
                    if (vertexOne == VisitLSN[i].vertex_one && vertexTwo == VisitLSN[i].vertex_two)
                    {
                        return i;
                    }
                }
            }
            return -1;
        }
        private void ShowTopologicalSort(Graphics g)
        {
            g.DrawLine(new Pen(Color.LightGray, 3), 0, An_Height - VertexSize - 15, An_Width, An_Height - VertexSize - 15);
            g.DrawString("拓朴序列：", new Font("微软雅黑", 15, FontStyle.Bold), Brushes.Red, 12, An_Height - 48);
            int x = 150;
            for (int i = 0; i < TopologicalSortResult.Length; ++i)
            {
                    DrawVertex(g, TopologicalSortResult[i].ToString(), VertexBmp[1], x, An_Height - VertexSize - 10);
                    x += VertexSize;
            }
        }
        /// <summary>
        /// 显示最小生成结果 
        /// </summary>
        private void ShowShortestTreeResult(Graphics g)
        {
            g.DrawLine(new Pen(Color.LightGray, 3), 0, An_Height - VertexSize - 15, An_Width, An_Height - VertexSize - 15);
            g.DrawString("最小生成树：", new Font("微软雅黑", 15, FontStyle.Bold), Brushes.Red, 12, An_Height - 48);
            string result = "";
            int r = 0;
            int i ;
            for (i = 0; i < VisitLSN.Count - 1; ++i)
            {
                result += VisitLSN[i].cost.ToString() + "[" + VisitLSN[i].vertex_one.ToString() + "," + VisitLSN[i].vertex_two.ToString() + "] + ";
                r += VisitLSN[i].cost;
            }
            if (VisitLSN.Count != 0)
            {
                r += VisitLSN[i].cost;
                result += VisitLSN[i].cost.ToString() + "[" + VisitLSN[i].vertex_one.ToString() + "," + VisitLSN[i].vertex_two.ToString() + "] = " + r.ToString();
                g.DrawString(result, new Font("微软雅黑", 12), Brushes.Yellow, 130, An_Height - VertexSize + 5);
            }
        }
        /// <summary>
        /// 用来画栈或队列
        /// </summary>
        private void DrawLineList(Graphics g, int x, int y, string name)
        {
            g.DrawLine(new Pen(Color.LightGray, 3), 0, y, An_Width, y);
            g.DrawString(name, new Font("微软雅黑", 15, FontStyle.Bold), Brushes.Red, 12, y + 15);
            for (int i = 0; i < LineList.Count; ++i)
            {
                int bmp_index = 0;
                if (i == 0)
                {
                    bmp_index = 2;
                }
                DrawVertex(g, LineList[i].ToString(), VertexBmp[bmp_index], x, y);
                x += VertexSize;
            }
        }
        /// <summary>
        /// 显示遍历的结果
        /// </summary>
        private void ShowTraversalResult(Graphics g)
        {
            String strResult = "";
            String strListName = "";
            if (operateType == GraphsOperateType.BFT)
            {
                strResult = "广度优先遍历：";
                strListName = "队             列：";
            }
            else
            {
                strResult = "深度优先遍历：";
                strListName = "堆             栈：";
            }
            int x = 150, y = An_Height - VertexSize - 10;
            //g.DrawLine(new Pen(Color.LightGray, 3), 0, An_Height - VertexSize*2 - 30, An_Width, An_Height - VertexSize*2 - 30);
            //g.DrawString(strListName, new Font("微软雅黑", 15, FontStyle.Bold), Brushes.Red, 12, An_Height - 48 - VertexSize - 15);
            DrawLineList(g, x, An_Height - VertexSize * 2 - 30, strListName); ;
            g.DrawLine(new Pen(Color.LightGray, 3), 0, An_Height - VertexSize - 15, An_Width, An_Height - VertexSize - 15);
            g.DrawString(strResult, new Font("微软雅黑", 15, FontStyle.Bold), Brushes.Red, 12, An_Height - 48);
            x = 150;
            for (int i = 0; i < visitResult.Length; ++i)
            {
                DrawVertex(g, visitResult[i].ToString(), VertexBmp[1], x, y);
                x +=  VertexSize;
            }
        }
        /// <summary>
        /// 设置圆的中心坐标和圆的半径(遍历和最小生成树等算法中心坐标和半径是不一样的)
        /// </summary>
        private void SetCenterPointAndRadius()
        {
            int w = 0;
            switch (operateType)
            {
                case GraphsOperateType.DFT:
                case GraphsOperateType.BFT:
                    radius = GetCircleRadius(this.An_Width, An_Height - VertexSize * 2 - 30);
                    CenterPt = new Point(this.An_Width / 2, this.An_Height / 2 - VertexSize / 2 - VertexSize - 15);
                    break;
                case GraphsOperateType.Prim:
                case GraphsOperateType.Kruskal:
                    w = this.An_Width - 255;
                    if (bMaximize)
                    {
                        w = this.An_Width - (VertexNum + 1) * Maxtrix_Elment_Size.Width;
                    }
                    radius = GetCircleRadius(w, An_Height - VertexSize - 15);
                    CenterPt = new Point(w / 2 - VertexSize / 2, (this.An_Height - VertexSize - 15) / 2- VertexSize / 2);
                    break;
                case GraphsOperateType.TopologicalSortCheckLoop:
                case GraphsOperateType.DFTCheckLoop:
                    radius = GetCircleRadius(this.An_Width, An_Height - VertexSize - 15);
                    CenterPt = new Point(this.An_Width / 2, (this.An_Height   - VertexSize * 2 - 15) / 2);
                    break;
                case GraphsOperateType.Dijkstra:
                case GraphsOperateType.Bellman_Ford:
                    VertexSize = 40;
                    w = this.An_Width - 255;
                    if (bMaximize)
                    {
                        w = this.An_Width - (VertexNum + 1) * Maxtrix_Elment_Size.Width;
                    }
                    radius = GetCircleRadius(w, An_Height - VertexSize - Form_Height);
                    CenterPt = new Point((w - VertexSize) / 2, (this.An_Height - Form_Height - VertexSize) / 2);
                    break;
             }
        }
        /// <summary>
        /// 显示图
        /// </summary>
        private void ShowGraphs(Graphics g)
        {
            if (VertexNum == 0)
            {
                return;
            }
            g.SmoothingMode = SmoothingMode.HighQuality;
            g.DrawImage(PublicDataClass.DemoPicture, 0, 0, An_Width, An_Height);
            //起始角度
            double degrees = 180.0;

            Point startPt = new Point();
            Point endPt = new Point();
            //画邻接边
            for (int i = 0; i < LSN.Count; ++i)
            {
                startPt = GetVertexPoint(LSN[i].vertex_one);
                startPt.X += VertexSize / 2;
                startPt.Y += VertexSize / 2;
                endPt = GetVertexPoint(LSN[i].vertex_two);
                endPt.X += VertexSize / 2;
                endPt.Y += VertexSize / 2;
                Pen LinePen = new Pen(Color.Blue, 3);
                Color costCol = Color.YellowGreen;
                if (!UnDirectGraph)//有向图
                { 
                    //有待添加箭头直线表示有向图
                    AdjustableArrowCap lineCap = new AdjustableArrowCap(4, 4);
                    LinePen.CustomEndCap = lineCap;
                    endPt = SetArrowPoint(startPt, endPt);
                }
                if (FindVisitSide(LSN[i].vertex_one, LSN[i].vertex_two) != -1)
                {
                    LinePen.Color = Color.LightGray;
                    costCol = Color.Red;
                }
                g.DrawLine(LinePen, startPt.X, startPt.Y, endPt.X, endPt.Y);
                if (!UnCost)//有权图
                {
                    int lineStart = (startPt.X + endPt.X) / 2;
                    int lineEnd = (startPt.Y + endPt.Y) / 2;
                    g.DrawString(LSN[i].cost.ToString(), new Font("微软雅黑", 15), new SolidBrush(costCol), lineStart, lineEnd);
                }
            }
            //根据图的结点数和圆画正几边形
            int x, y;
            double angle;
            double offsetDegrees = 360.0 / VertexNum;
            for (int i = 0; i < VertexNum; ++i)
            {
                angle = GetAngle(degrees);
                x = CenterPt.X + (int)(radius * Math.Cos(angle));
                y = CenterPt.Y + (int)(radius * Math.Sin(angle));
                DrawVertex(g, i.ToString(), VertexBmp[visit[i]], x, y);
                degrees += offsetDegrees;
            }
            if (operateType == GraphsOperateType.DFT)
            {
                Point PtrPt = GetVertexPoint(PtrVertex);
                g.DrawImage(arrowBmp, PtrPt.X + VertexSize/2 - 8, PtrPt.Y - 16, 16, 16);
            }
            if(operateType == GraphsOperateType.BFT || operateType == GraphsOperateType.DFT)
            ShowTraversalResult(g);
            if (operateType == GraphsOperateType.Prim || operateType == GraphsOperateType.Kruskal)
            {
                if (bMaximize)
                {
                    DrawGraphMaxtrix(g,
                                        this.An_Width - (VertexNum + 1) * Maxtrix_Elment_Size.Width, (this.An_Height - 125) / 2 - Maxtrix_Elment_Size.Height * VertexNum / 2);
                }
                else
                {
                    ShowCostEdges(g, VertexSize + 15, true);
                }
                ShowShortestTreeResult(g);
            }
            if (operateType == GraphsOperateType.Dijkstra || operateType == GraphsOperateType.Bellman_Ford)
            {
                if (bMaximize)
                {
                    DrawGraphMaxtrix(g,
                                        this.An_Width - (VertexNum + 1) * Maxtrix_Elment_Size.Width, (this.An_Height  - 245)/ 2 - Maxtrix_Elment_Size.Height * (VertexNum - 1)/ 2);
                }
                else
                {
                    ShowCostEdges(g, 245, false);
                }
                DrawForm(g);
                ShowShortPath(g);
            }
            if (operateType == GraphsOperateType.TopologicalSortCheckLoop)
            {
                ShowTopologicalSort(g);
            }
            if (operateType == GraphsOperateType.DFTCheckLoop)
            {
                DrawLineList(g, 150, An_Height - VertexSize - 15, "堆             栈：");
            }
        }
        private void DrawEdgesRect(Graphics g, Color bkCol, int x, int y, int w, int h)
        {
            g.FillRectangle(new SolidBrush(Color.FromArgb(100, bkCol)), x, y, w, h);
            g.DrawRectangle(new Pen(Brushes.Green, 2), x, y, w, h);
        }
        /// <summary>
        /// 显示有权边，用于Prim和Kruskal算法
        /// </summary>
        private void ShowCostEdges(Graphics g, int offset_y, bool bOrder)
        {
            int x = An_Width - 255;
            int y = 0;
            int EdgeRectHeight = (An_Height - offset_y) / (LSN.Count + 1);
            DrawEdgesRect(g, Color.YellowGreen,  x, y, 250, EdgeRectHeight);
            g.DrawString("No.   v1<-->v2 cost order", new Font("微软雅黑", 15), Brushes.Red, x, y + EdgeRectHeight/ 2 - 15);
            y = EdgeRectHeight;
            int visitOrder = -1;
            Color bkCol;
            Color fontCol;
            for (int i = 0; i < LSN.Count; ++i)
            {
                bkCol = Color.YellowGreen;
                fontCol = Color.Yellow;
                if (bOrder)
                {
                    visitOrder = FindVisitSide(LSN[i].vertex_one, LSN[i].vertex_two);
                    if (visitOrder != -1)
                    {
                        bkCol = Color.Blue;
                        fontCol = Color.White;
                    }
                    else
                    {
                        visitOrder = -1;
                    }
                }
                DrawEdgesRect(g, bkCol, x, y + i*EdgeRectHeight, 250, EdgeRectHeight);
                string strEdge = string.Format("{0:D2}     {1,2}<-->{2,2}    {3:D2}  {4,4}", i + 1, LSN[i].vertex_one, LSN[i].vertex_two, LSN[i].cost, visitOrder + 1);
                g.DrawString(strEdge, new Font("微软雅黑", 15), new SolidBrush(fontCol), x, y +i*EdgeRectHeight+ EdgeRectHeight / 2 - 15);
            }
        }
        /// <summary>
        /// 画顶点
        /// </summary>
        private void DrawVertex(Graphics g, String vertex, Bitmap vBmp, int x, int y)
        {
            g.DrawImage(vBmp, x, y, VertexSize, VertexSize);
            g.DrawString(vertex, new Font("微软雅黑", (float)0.45 * VertexSize, FontStyle.Bold), Brushes.White, 
                x + VertexSize / 2 - (int)(0.6 * VertexSize / 2), y + (int)(0.15*VertexSize));
        }
        /// <summary>
        /// 初始化图的矩阵
        /// </summary>
        private void InitGraphsMaxtrix()
        {
            for (int i = 0; i < VertexNum; ++i)
            {
                for (int j = 0; j < VertexNum; ++j)
                {
                    GraphMatrix[i, j] = 0;
                }
            }
        }
        /// <summary>
        /// 根据图给矩阵赋值
        /// </summary>
        private void SetGraphsMaxtrix()
        {
            int m,n;
            for (int i = 0; i < LSN.Count; ++i)
            {
               m = LSN[i].vertex_one;
               n = LSN[i].vertex_two;
               GraphMatrix[m, n] = LSN[i].cost;
               if (UnDirectGraph)
               {
                   GraphMatrix[n, m] = LSN[i].cost;
                }
            }
        }
        private void Refresh()
        {
            try
            {
                if (An_Form.IsHandleCreated)
                    An_Form.Invoke(An_Handler);
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }
        }
        /// <summary>
        /// 画一个表格，来显示最短路径的相关信息
        /// </summary>
        private void DrawForm(Graphics g)
        {
            int x = 0;
            int y = this.An_Height - Form_Height;
            int offset_x = this.An_Width / VertexNum;
            int offset_y = Form_Height / (VertexNum + 2);
            if (0 == VertexNum)
            {
                return;
            }
            g.DrawString("v0 -> v", new Font("微软雅黑", 14), Brushes.Yellow, x, y);
            //画四条横线
            for (int i = 0; i < VertexNum + 2; ++i)
            {
                g.DrawLine(Pens.Yellow, x, y, x + this.An_Width, y);
                y += offset_y;
            }
            y = this.An_Height - Form_Height;
            x = offset_x;
            //花纵线
            for(int j = 0; j < VertexNum - 1; ++j)
            {
                g.DrawLine(Pens.Yellow, x, y, x, y + Form_Height);
                g.DrawString("v"+(j+1).ToString(), new Font("微软雅黑", 14), Brushes.Yellow, x, y);
                x += offset_x;
            }
        }
        private void DrawShortPath(Graphics g, string str_shortPath, int dist, int vertex)
        {
            int offset_x = this.An_Width / VertexNum;
            int offset_y = Form_Height / (VertexNum + 2);
            int x = offset_x * vertex;
            int y = this.An_Height - Form_Height;

            string str_dist = "";
            if (0 == dist)
            {
                str_dist = "∞";
            }
            else
            {
                str_dist = dist.ToString();
            }
            g.DrawString(str_dist, new Font("微软雅黑", 14), Brushes.Yellow, x, y + offset_y);
            g.DrawString(str_shortPath, new Font("微软雅黑", 14), Brushes.Yellow, x, y + offset_y*2);
        }
        /// <summary>
        /// 显示Dijkstra最短路径
        /// </summary>
        private void ShowShortPath(Graphics g)
        {
            int offset_x = this.An_Width / VertexNum;
            int offset_y = Form_Height / (VertexNum + 2);
            int x = 0;
            int y = this.An_Height - Form_Height + offset_y;
            Brush fontBrush = null;
            for (int i = 0; i < Save_Path.Count; ++i)
            {
                string[] short_path = Save_Path[i].Split(',');
                for (int j = 0; j < short_path.Length; ++j)
                {
                    fontBrush = Brushes.Yellow;
                    if (Save_Path.Count > 2 && i == Save_Path.Count - 2 )
                    {
                        string[] temp = Save_Path[i - 1].Split(',');
                        if (temp[j] != short_path[j])
                        {
                            fontBrush = Brushes.Red;
                        }
                    }
                    string cost = "0";
                    if(operateType == GraphsOperateType.Bellman_Ford)
                    {
                        cost = "500";
                    }
                    if (short_path[j] ==  cost&& i != Save_Path.Count - 1)
                    {
                        short_path[j] = "∞";
                    }
                    g.DrawString(short_path[j], new Font("微软雅黑", 14), fontBrush, x + j * offset_x, y + offset_y * i);
                }
            }
        }
        private void DrawGraphMaxtrix(Graphics g, int x, int y)
        {
            //矩阵的[
            g.DrawLine(Pens.Yellow, x, y, x - 10, y + 10);
            g.DrawLine(Pens.Yellow, x - 10, y + 10, x - 10, y + Maxtrix_Elment_Size.Height * (VertexNum - 1) + 10);
            g.DrawLine(Pens.Yellow, x - 10, y + Maxtrix_Elment_Size.Height * (VertexNum - 1) + 10, x, y + Maxtrix_Elment_Size.Height * (VertexNum - 1) + 20);
            int temp_x = x;
            int temp_y = y;
            for (int i = 0; i < VertexNum; ++i)
            {
                g.DrawString(i.ToString(), new Font("微软雅黑", 15), Brushes.Red, x + i * Maxtrix_Elment_Size.Width, y - 30);
                g.DrawString(i.ToString(), new Font("微软雅黑", 15), Brushes.Red, x - 30, y + Maxtrix_Elment_Size.Height *i);
                temp_x = x;
                string cost = "0";
                for (int j = 0; j < VertexNum; ++j)
                {
                    if (0 == GraphMatrix[i, j] && i != j)
                    {
                        cost = "∞";
                    }
                    else
                    {
                        cost = GraphMatrix[i, j].ToString();
                    }
                    g.DrawString(cost, new Font("微软雅黑", 15), Brushes.Yellow, temp_x, temp_y);
                    temp_x += Maxtrix_Elment_Size.Width; ;
                }
                temp_y += Maxtrix_Elment_Size.Height; ;
            }
            x += Maxtrix_Elment_Size.Width * VertexNum - 20;
            g.DrawLine(Pens.Yellow, x , y, x + 10, y + 10);
            g.DrawLine(Pens.Yellow, x + 10, y + 10, x + 10, y +  (VertexNum - 1) * Maxtrix_Elment_Size.Height + 10);
            g.DrawLine(Pens.Yellow, x + 10, y + (VertexNum - 1) * Maxtrix_Elment_Size.Height + 10, x, y + (VertexNum - 1) * Maxtrix_Elment_Size.Height + 20);
        }
        private int FindShortPath()
        {
            int min_cost = MAX_COST;
            int index = -1;
            for (int i = 0; i < vertexs.Count; ++i)
            {
                for (int j = 1; j < VertexNum; ++j)
                {
                    int cost = GraphMatrix[vertexs[i], j];
                    if (cost != 0)
                    {
                        if (min_cost > cost && !IsVertexExsit(j))
                        {
                            min_cost = cost;
                            index = j;
                        }
                    }
                }
            }
            return index;
        }
        private void SaveShortPath(int vertex)
        {
            if (0 != Save_Path.Count)
            {
                Save_Path.RemoveAt(Save_Path.Count - 1);
            }
            string strdist = vertex.ToString() + " dist,";
            if (operateType == GraphsOperateType.Bellman_Ford)
            {
                strdist = (vertex + 1).ToString() + ",";
            }
            string strpath = "path,";
            for (int i = 0; i < ShortPathes.Length; ++i)
            {
                strpath += ShortPathes[i].path.ToString();
                strdist += ShortPathes[i].dist.ToString(); 
                if (i < ShortPathes.Length - 1)
                {
                    strpath += ",";
                    strdist += ",";
                }
            }
            Save_Path.Add(strdist);
            Save_Path.Add(strpath);
        }
        /// <summary>
        /// Dijkstra计算最短路径
        /// </summary>
        private void Dijkstra()
        {
            vertexs.Clear();
            SetExcuteLine(4);
            vertexs.Add(0);
            SetExcuteLine(5);
            for (int i = 0; i < VertexNum - 1; ++i)
            {
                SetExcuteLine(8);
                int index = FindShortPath();
                SetExcuteLine(9);
                if (-1 != index)
                {
                    SetExcuteLine(12);
                    vertexs.Add(index);
                    visit[index] = 2;
                    Visit();
                    SetExcuteLine(14);
                    ResetShortPath(index);
                    SaveShortPath(index);
                    visit[index] = 1;
                    Visit();
                }
                else
                {
                    SetExcuteLine(18);
                    break ;
                }
                SetExcuteLine(5);
            }
            SetExcuteLine(21);
            Visit();
            MessageBox.Show(An_Form, "Dijkstra动画演示结束");
        }
        /// <summary>
        /// Bellman-Ford求任意权值的不含负权值的回路的最短路径
        /// </summary>
        private void Bellman_Ford()
        {
            int[] dist = new int[VertexNum - 1];
            SetExcuteLine(3);
            SetExcuteLine(4);
            for (int i = 2; i < VertexNum; ++i)
            {
                for (int u = 0; u < VertexNum - 1; ++u)
                {
                    dist[u] = ShortPathes[u].dist;
                }
                SetExcuteLine(5);
                for (int j = 0; j < VertexNum - 1; ++j)
                {
                    int w = dist[j];
                    SetExcuteLine(6);
                    visit[j + 1] = 1;
                    Visit();
                    for (int k = 1; k < VertexNum; ++k)
                    {
                        SetExcuteLine(7);
                        if (ShortPathes[j].vertex != k)
                        {
                            visit[k] = 2;
                            SetExcuteLine(9);
                            int cost = GraphMatrix[k, ShortPathes[j].vertex];
                            SetExcuteLine(10);
                            if (cost != 0 && w > dist[k - 1] + cost)
                            {
                                RemoveVisitLSN(ShortPathes[j].path, ShortPathes[j].vertex);
                                w = dist[k - 1] + cost;
                                SetExcuteLine(12);
                                ShortPathes[j].dist = dist[k - 1] + cost;
                                SetExcuteLine(13);
                                ShortPathes[j].path = k;
                                VisitLSN.Add(new LineSideVertex(ShortPathes[j].path, ShortPathes[j].vertex, cost));
                            }
                            Visit();
                            visit[k] = 0;
                        }
                        SetExcuteLine(6);
                    }
                    SetExcuteLine(5);
                    visit[j + 1] = 0;
                }
                SetExcuteLine(4);
                SaveShortPath(i - 1);
                Visit();
            }
            SetExcuteLine(16);
            MessageBox.Show(An_Form, "演示结束");
        }
        private void RemoveVisitLSN(int vertex_one, int vertex_two)
        {
            for (int i = 0; i < VisitLSN.Count; ++i)
            {
                if (vertex_one == VisitLSN[i].vertex_one && vertex_two == VisitLSN[i].vertex_two)
                {
                    VisitLSN.RemoveAt(i);
                    return;
                }
            }
        }
        /// <summary>
        /// 得到最短路径的顶点，重新设置相关的路径
        /// </summary>
        private void ResetShortPath(int vertex)
        {
            for (int i = 0; i < VertexNum - 1; ++i)
            {
                if (ShortPathes[i].vertex != vertex)
                {
                    if (0 != GraphMatrix[vertex, ShortPathes[i].vertex])
                    {
                        if (0 == ShortPathes[i].dist || ShortPathes[i].dist > ShortPathes[vertex - 1].dist + GraphMatrix[vertex, ShortPathes[i].vertex])
                        {
                            if (0 != ShortPathes[i].dist)
                            {
                                RemoveVisitLSN(ShortPathes[i].path, ShortPathes[i].vertex);
                            }
                            ShortPathes[i].dist = ShortPathes[vertex - 1].dist + GraphMatrix[vertex, ShortPathes[i].vertex];
                            ShortPathes[i].path = vertex;
                            VisitLSN.Add(new LineSideVertex(vertex, ShortPathes[i].vertex, GraphMatrix[vertex, ShortPathes[i].vertex]));
                        }
                    }
                }
            }
        }
        /// <summary>
        /// 初始化最短路径一些相关值
        /// </summary>
        private void InitShortPath()
        {
            Save_Path.Clear();
            string strdist = "0 dist,";
            if (operateType == GraphsOperateType.Bellman_Ford)
            {
                strdist = "1,";
            }
            string strpath = "path,";
            for (int i = 1; i <= ShortPathes.Length; ++i)
            {
                //cost = 0为无穷大
                int cost = GraphMatrix[0, i];
                if (cost == 0)
                {
                    strpath += "-1";
                    cost = MAX_COST;
                    ShortPathes[i - 1].SetValues(i, MAX_COST, -1);
                }
                else
                {
                    strpath += "0";
                    ShortPathes[i - 1].SetValues(i, cost, 0);
                }
                strdist += cost.ToString();
                if (i < ShortPathes.Length)
                {
                    strpath += ",";
                    strdist += ",";
                }
                if (MAX_COST != cost)
                {
                    VisitLSN.Add(new LineSideVertex(0, i, cost));
                }
            }
            visit[0] = 2;
            Save_Path.Add(strdist);
            Save_Path.Add(strpath);
        }
        /// <summary>
        /// 接口的初始化函数
        /// </summary>
        public void InitData()
        {
            operateType = GlobalGraphs.OperatType;
            VertexNum = GlobalGraphs.VertexNum;
            UnCost = GlobalGraphs.UnCost;
            UnDirectGraph = GlobalGraphs.UnDirect;
            LSN.Clear();
            GlobalGraphs.LSN.ForEach(i => LSN.Add(i));
            //如果是Kruskal算法时
            if (operateType == GraphsOperateType.Kruskal)
            {
                InitCCVertexs();
            }
            GraphMatrix = new int[VertexNum, VertexNum];
            InitGraphsMaxtrix();
            SetGraphsMaxtrix();
            visit = new int[VertexNum];
            VisitLSN.Clear(); 
            if (operateType == GraphsOperateType.Dijkstra || operateType == GraphsOperateType.Bellman_Ford)
            {
                ShortPathes = new ShortPath[VertexNum - 1];
                InitShortPath();
            }
            SetCenterPointAndRadius();
            visitResult = "";
            LineListClear();
            ShowGraphs(BufferGraph);
            Visit();
        }
        /// <summary>
        /// 接口的动画函数
        /// </summary>
        public void Animation()
        {
            //ResetData();
            switch (operateType)
            {
                case GraphsOperateType.BFT:
                    BFT(); break;
                case GraphsOperateType.DFT:
                    DFT();break;
                case GraphsOperateType.Prim:
                    Prim();break;
                case GraphsOperateType.Kruskal:
                    Kruskal(); break;
                case GraphsOperateType.TopologicalSortCheckLoop:
                    TopologicalSortCheckLoop(); break;
                case GraphsOperateType.DFTCheckLoop:
                    DFTCheckLoop(); break;
                case GraphsOperateType.Dijkstra:
                    Dijkstra(); break;
                case GraphsOperateType.Bellman_Ford:
                    Bellman_Ford(); break;
            }
            SysMainForm.AnimationForm.ChangeExcuteOverBtnsEnable();
        }
        /// <summary>
        /// 接口的重新设置数据函数
        /// </summary>
        public void ResetData()
        {
            visitResult = "";
            TopologicalSortResult = "";
            InitVisit();
            VisitLSN.Clear();
            InitCCVertexs();
            InitGraphsMaxtrix();
            SetGraphsMaxtrix();
            if (operateType == GraphsOperateType.Dijkstra || operateType == GraphsOperateType.Bellman_Ford)
            {
                Save_Path.Clear();
                InitShortPath();
            }
            ShowGraphs(BufferGraph);
            Refresh();
        }
        /// <summary>
        /// 接口的重新设置双缓冲画布函数
        /// </summary>
        public void ResetBuffer(int Width, int Height)
        {
            if (0 == Width || 0 == Height)
            {
                return;
            }
            //判断最大化
            if (Width > An_Width)
            {
                bMaximize = true;
            }
            else
            {
                bMaximize = false;
            }
            An_Width = Width;
            An_Height = Height;
            //重新设置画布
            if(null != BufferBmp)
            {
                BufferBmp.Dispose();
            }
            BufferBmp = new Bitmap(Width, Height);
            if(null != BufferGraph)
            {
                BufferGraph.Dispose();
            }
            BufferGraph = Graphics.FromImage(BufferBmp);
            SetCenterPointAndRadius();
            ShowGraphs(BufferGraph);
        }
        /// <summary>
        /// 接口的得到画布函数
        /// </summary>
        public Bitmap GetBufferBmp()
        {
            return BufferBmp;
        }
        public void SetSpeed(float scale)
        {
            Speed = (int)(DEFAULT_SPEED * scale);
        }
    }
}